% This function removes all pendant vertices from undirected graph G
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function Gstar = GtoGstar(mAdjUndirected,varargin)
%  
%   This function is a helper function for finding if a graph is Eulerian
%   or Hamiltonian.  It takes an input graph of G, which is the adjacency
%   matrix for an undirected graph, and will output a reduced G*, which
%   excludes all vertices with only 1 edge connected to them.
%
%   INPUTS:     mAdjUndirected - Adjacency Matrix for Undirected Graph G
%   
%   OUTPUTS:    Gstar - G after removal of all pendant vertices
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function Gstar = GtoGstar(mAdjUndirected,varargin)

% First up let us search for all indexes that need removal
% And make excludedArray to keep track of any vertices with one edge
excludedArray = zeros(1,60);
gPartialSize = 60;

for x=1:60
    % add all the way across a row
    sum = 0;
    for y=1:60
        sum = sum + mAdjUndirected(x,y);        
    end;
    % if the vertex has only 1 edge connected, exclude it
    if (sum <= 1),
        excludedArray(x) = 1;
        gPartialSize = gPartialSize - 1;
    end;
end;

% Now we create gPartialRemove, which is mostly just skipping rows and
% direct copying from G
gPartialRemove = zeros(gPartialSize,60);
n = 1;
for x=1:60
    % If the row isn't set to be excluded, add it to gPartialRemove
    if (excludedArray(x) == 0),
        for y=1:60
            gPartialRemove(n,y) = mAdjUndirected(x,y);            
        end;
        % Since n doesn't always increment, we can't increment it
        % automatically by loop so we must add one for the next row
        n = n + 1;
    end;
end;

% Now we have the partial matrix with extra vertices and we must trim it
% down.
    
Gstar = zeros(gPartialSize,gPartialSize);

for x=1:gPartialSize
    % If the row isn't set to be excluded, add it to gPartialRemove
    n = 1;
    for y=1:60
        if (excludedArray(y) == 0),
            % We need this element, so add it to Gstar
            % Also need to manually increase the index
            Gstar(x,n) = gPartialRemove(x,y);
            n = n + 1;            
        end;
    end;
end;

